package leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述:236. 二叉树的最近公共祖先
 *
 * @author Madison You
 * @created 10:43
 */
public class Mid_236_LowestCommonAncestor {
    public static void main(String[] args) {
        TreeNode treeNode = CreateTreeNode.arrayToTreeNode(new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4});
        TreeNode treeNode1 = CreateTreeNode.arrayToTreeNode(new Integer[]{5, 6, 2, null, null, 7, 4});
        TreeNode treeNode2 = CreateTreeNode.arrayToTreeNode(new Integer[]{1, 0, 8});
        new Mid_236_LowestCommonAncestor().lowestCommonAncestor(treeNode, treeNode1, treeNode2);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { // 递归结束条件
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

}
